package com.leetcode.滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//找到字符串中所有字母异位词
public class lc_438 {
    public static void main(String[] args) {
        String s = "abab";
        String p = "ab";
        System.out.println(findAnagrams2(s, p));
        System.out.println(findAnagrams3(s, p));
    }

    //给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        //将每一个滑动窗口中的元素进行排序,如果相等,就放入集合
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        Arrays.sort(pArr);
        int left = 0, right = pArr.length - 1;
        for (left = 0; left < sArr.length - pArr.length + 1; left++, right++) {
            char[] tempArr = new char[pArr.length];
            for (int i = 0; i < p.length(); i++) {
                tempArr[i] = sArr[left + i];
            }
            Arrays.sort(tempArr);
            if (Arrays.equals(pArr, tempArr)) {
                res.add(left);
            }
        }
        return res;
    }

    public static List<Integer> findAnagrams2(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();  //  arraylist是有序的，有索引的
        int[] sCount = new int[26];  // 整数，记录26个小写字母的索引，a对应索引0，b对应索引1..... 每个索引对应的值，为该字母出现的次数，初始次数都是0；
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; i++) { // 按照p字符数组的长度去遍历
            ++sCount[s.charAt(i) - 'a']; // s.chartAt(i)得到此处的字母，-"a"，得到该字母的索引，++表示统计该字母的出现次数。
            ++pCount[p.charAt(i) - 'a'];
        }
        //判断放置处是否有异位词。若相等，则表明s的前几位就是p的异位词。起始索引即为0.
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a']; // 减去滑动窗口的第0位，即，窗口变为1，2
            ++sCount[s.charAt(i + pLen) - 'a']; // 加上窗口的第plen位(第3位)，即，窗口变为1，2，3
            // 完成了一次滑动窗口
            // 若相等，存在异位词，起始索引为i+1
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

    public static List<Integer> findAnagrams3(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<>();
        //使用数组存储
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //记录s和p在此次滑动窗口中各个字母的位数
        for (int i = 0; i < pLen; i++) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
        //判断起始滑动窗口是否为字母异位词
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[p.charAt(i + pLen) - 'a'];
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}
